class Solution {
public:
    int dir[4][2] = {
        {0, 1}, {0, -1}, {1, 0}, {-1, 0}
    };
    int dfs(vector<vector<int>> &grid, int x, int y) {
        if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == 0) {
            return 1;
        }
        if (grid[x][y] == 2) return 0;
        grid[x][y] = 2;
        int res = 0;
        for (int k = 0; k < 4; k++) {
            int dx = x + dir[k][0];
            int dy = y + dir[k][1];
            res += dfs(grid, dx, dy);
        }
        return res;
    }
    int islandPerimeter(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    ans += dfs(grid, i, j);
                }
            }
        }
        return ans;
    }
};
